1. Field of the Invention
The present invention relates to a shared buffer switch, and more particularly, to a buffer partitioning method for a shared buffer switch and a shared buffer switch which is used in the method.
2. Description of the Related Art
A network which transfers data among communications apparatuses includes a plurality of switching nodes. Shared buffer switches are widely used as switching nodes. Since the size of a shared buffer is limited, unless the shared buffer is partitioned appropriately with respect to the traffic volume of inflowing cells and the operating environments, the performance of the switch will be degraded. That is, under the same hardware environments, the cell loss ratio and buffer utilization ratio will differ according to a shared buffer partitioning method.
Among prior art methods for efficiently partitioning a shared buffer, there are a virtual partitioning method, a dynamic threshold method, and a dynamic partitioning method.
The virtual partitioning method (U.S. Pat. No. 5,909,547) uses a plurality of port thresholds, each of which is allocated for an output port, and an entire buffer threshold which is assigned to the buffer. If the number of cells currently stored in a buffer for an output port is less than the port threshold of the output port, and the number of cells currently stored in the entire buffer is less than the entire buffer threshold, the state is referred to as an underload state, and if the number of cells currently stored in a buffer for an output port is greater than the port threshold of the output port, but the number of cells currently stored in the entire buffer is less than the entire buffer threshold, the state is referred to as an overload state. When a cell arrives to an output port, if the output port is in an underload or overload state, the cell is stored in the buffer, and otherwise the cell is discarded.
Since the virtual partitioning method uses a fixed threshold for each output port, it is difficult for the method to be actively adapted to the external condition changes such as backpressure. In addition, since it is difficult to predetermine thresholds for traffic whose variables cannot be specified in advance such as Unspecified Bit Rate (UBR) traffic, the method cannot be applied to such traffics. Furthermore, since the method uses only the total number of the cells as the criterion, it is difficult for the method to be swiftly adapted to traffic changes and external conditions change.
The dynamic threshold method (U.S. Pat. No. 5,541,912) divides a shared buffer into a reserved area, and available areas, each of which is assigned to an output port. In the method, if an output port has waiting cells, it is referred to as an active output port. The threshold of the active output port is a value obtained by dividing the size of the whole available area by the number of active output ports. If the number of cells currently waiting in an available area is equal to or greater than the threshold of the corresponding output port, newly arriving cells are discarded, and otherwise newly arriving cells are stored in the available area. The reserved area is provided for a buffering effect which prevents sudden changes of threshold values when an output port which was not active becomes an active port.
In the dynamic threshold method, if inflowing traffic or a service rate differs for each active output port, utilization ratio of the buffer decreases. For example, even when an inflowing traffic is small for one output port, since the allocated buffer areas have same sizes for all output ports, the buffer area allocated to the output port of small inflowing traffic has many wasted parts. Also, for an output port for which the inflowing traffic is greater than the outflowing traffic, or for an output port which is in a backpressure state, the number of cells waiting in buffer area increases, while the same size buffer is allocated to output ports whose amount of inflowing traffic is small. Therefore, even when many empty spaces are available in a shared buffer, cell loss may occur, and the method cannot be promptly adapted to traffic changes and external conditions change.
The dynamic partitioning method (S. Krishnan et al, Dynamic Partitioning: A Mechanism for Shared Memory Management, INFOCOM '99. Eighteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Proceedings., Vol. 1, 1999) divides a load state into an overload state and an underload state based on the total number of cells waiting in a shared buffer, and makes a cell discard threshold of each virtual circuit has a different value in each state. In order to prevent a sudden change of the threshold due to a load state change, a threshold between each state is calculated by interpolation. When a new cell arrives, if the number of cells stored in a buffer area corresponding to a virtual circuit in which the cell is included is less than the threshold of the virtual circuit, and the total number of cells stored in the shared buffer is less than the size of the shared buffer, the new cell is stored in the shared buffer and otherwise the new cell is discarded.
The dynamic partitioning method uses interpolation to prevent a sudden change in a threshold, so the method needs complicated hardware for a plurality of multiplication and division, and high speed operation may be difficult. Since a cell discard threshold differs according to the service rate of each virtual circuit, a storage means is needed for storing an underload state and an overload state for each service rate. Also, since a cell discard threshold is determined only by the total number of cells, the method cannot be adapted to traffic changes and external environment changes.